{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Index of the First Occurrence in a String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string #string-matching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串 #字符串匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: strStr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出字符串中第一个匹配项的下标"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串&nbsp;<code>haystack</code> 和 <code>needle</code> ，请你在 <code>haystack</code> 字符串中找出 <code>needle</code> 字符串的第一个匹配项的下标（下标从 0 开始）。如果&nbsp;<code>needle</code> 不是 <code>haystack</code> 的一部分，则返回&nbsp; <code>-1</code><strong> </strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>haystack = \"sadbutsad\", needle = \"sad\"\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>\"sad\" 在下标 0 和 6 处匹配。\n",
    "第一个匹配项的下标是 0 ，所以返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>haystack = \"leetcode\", needle = \"leeto\"\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>\"leeto\" 没有在 \"leetcode\" 中出现，所以返回 -1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= haystack.length, needle.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>haystack</code> 和 <code>needle</code> 仅由小写英文字符组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-index-of-the-first-occurrence-in-a-string](https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-index-of-the-first-occurrence-in-a-string](https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"sadbutsad\"\\n\"sad\"', '\"leetcode\"\\n\"leeto\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        for i in range(len(haystack)):\n",
    "            if haystack[i:i+len(needle)] == needle:\n",
    "                return i\n",
    "        return -1\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    haystack = \"leetcode\"\n",
    "    needle = \"leeto\"\n",
    "    solution = Solution()\n",
    "    result = solution.strStr(haystack,needle)\n",
    "    print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack, needle):\n",
    "        \"\"\"\n",
    "        :type haystack: str\n",
    "        :type needle: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # return haystack.find(needle)\n",
    "        for i in range(len(haystack)):\n",
    "            if haystack[i:i+len(needle)] == needle:\n",
    "                return i\n",
    "        return 0 if haystack==\"\" and needle==\"\" else -1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack, needle):\n",
    "        \"\"\"\n",
    "        :type haystack: str\n",
    "        :type needle: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(haystack) < len(needle):\n",
    "            return -1\n",
    "        if needle == \"\":\n",
    "            return 0\n",
    "        for i in range(len(haystack) - len(needle) + 1):\n",
    "            find = False\n",
    "            for j in range(len(needle)):\n",
    "                if haystack[i + j] != needle[j]:\n",
    "                    find = False\n",
    "                    break\n",
    "                find = True\n",
    "            if find:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack, needle):\n",
    "        \"\"\"\n",
    "        :type haystack: str\n",
    "        :type needle: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        p1 = 0\n",
    "        p2 = len(needle)\n",
    "        if needle == '':\n",
    "            return 0\n",
    "        while p2 <= len(haystack):\n",
    "            if haystack[p1:p2] == needle:\n",
    "                return p1\n",
    "            else:\n",
    "                p1 += 1\n",
    "                p2 += 1\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack, needle):\n",
    "        \"\"\"\n",
    "        :type haystack: str\n",
    "        :type needle: str\n",
    "        :rtype: int\n",
    "        \"\"\" \n",
    "        if haystack=='' and needle=='':\n",
    "            return  0\n",
    "        if haystack=='':\n",
    "            return -1\n",
    "        if needle=='':\n",
    "            return 0\n",
    "        \n",
    "        len_ned=len(needle)\n",
    "        len_hay=len(haystack)\n",
    "        \n",
    "        if len_ned>len_hay:return -1\n",
    "        \n",
    "        pos=-1\n",
    "        \n",
    "        for i in range(0,len_hay-len_ned+1):\n",
    "            cur=haystack[i:i+len_ned]\n",
    "            if cur==needle:\n",
    "                pos=i\n",
    "                break\n",
    "        return pos\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack, needle):\n",
    "        \"\"\"\n",
    "        :type haystack: str\n",
    "        :type needle: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        for i in range(0, len(haystack) - len(needle) + 1):\n",
    "            if haystack[i:i+len(needle)] == needle:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack, needle):\n",
    "        \"\"\"\n",
    "        :type haystack: str\n",
    "        :type needle: str\n",
    "        :rtype: int\n",
    "        \"\"\"        \n",
    "        haystack = list(haystack)\n",
    "        needle = list(needle)\n",
    "        #needle judge empty\n",
    "        if(len(needle)==0):\n",
    "            return 0        \n",
    "        \n",
    "        if(len(haystack)==0):\n",
    "            return -1\n",
    "        \n",
    "        if(len(needle)>len(haystack)):\n",
    "            return -1\n",
    "        \n",
    "        for i in range(len(haystack)):\n",
    "            # if(haystack[i]==needle[0]):\n",
    "            # for j in range(len(needle)):\n",
    "            #     if(haystack[i]!=needle[j]):\n",
    "            #         break;\n",
    "            if((i+len(needle))>len(haystack)):\n",
    "                break;\n",
    "            if(haystack[i:i+len(needle)]==needle):\n",
    "                return i    \n",
    "        return -1\n",
    "\n",
    "                        \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack, needle):\n",
    "        \"\"\"\n",
    "        :type haystack: str\n",
    "        :type needle: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(needle) == 0:\n",
    "            return 0\n",
    "        elif len(needle) > len(haystack):\n",
    "            return -1\n",
    "        i = 0\n",
    "        while i <= (len(haystack) - len(needle)):\n",
    "            xiangdeng = True\n",
    "            # print(\"第\",i,\"个字母\",len(haystack))\n",
    "            if haystack[i] == needle[0]:\n",
    "                for j in range(len(needle)):\n",
    "                    if (i + j) < len(haystack) and (needle[j] != haystack[i+j]):\n",
    "                        print(\" \",i,j)\n",
    "                        xiangdeng = False\n",
    "                        break\n",
    "                print(xiangdeng)\n",
    "                if xiangdeng == True:\n",
    "                    return i\n",
    "                i += 1\n",
    "                # print(\"字符串不匹配\",i)\n",
    "            else:\n",
    "                i += 1\n",
    "                # print(\"首字母不对\",i)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack, needle):\n",
    "        \"\"\"\n",
    "        :type haystack: str\n",
    "        :type needle: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(haystack)\n",
    "        m = len(needle)\n",
    "        if m == 0:\n",
    "            return 0\n",
    "        elif m > n:\n",
    "            return -1\n",
    "        \n",
    "        # naive\n",
    "        # for i in range(n - m + 1):\n",
    "        #     match = True\n",
    "        #     for j in range(m):\n",
    "        #         if needle[j] != haystack[i + j]:\n",
    "        #             match = False\n",
    "        #             break\n",
    "        #     if match:\n",
    "        #         return i\n",
    "        # return -1\n",
    "        \n",
    "        # Rabin-Karp\n",
    "        # d, q, h = 256, 101, 1\n",
    "        # for i in range(m - 1):\n",
    "        #     h = h * d % q\n",
    "        # p, t = 0, 0\n",
    "        # for i in range(m):\n",
    "        #     p = (p * d + ord(needle[i])) % q\n",
    "        #     t = (t * d + ord(haystack[i])) % q\n",
    "        # for i in range(n - m + 1):\n",
    "        #     if p == t:\n",
    "        #         match = True\n",
    "        #         for j in range(m):\n",
    "        #             if needle[j] != haystack[i + j]:\n",
    "        #                 match = False\n",
    "        #                 break\n",
    "        #         if match:\n",
    "        #             return i\n",
    "        #     elif i < n - m:\n",
    "        #         t = (t - ord(haystack[i]) * h) * d + ord(haystack[i + m])\n",
    "        #         while t < 0:\n",
    "        #             t += q\n",
    "        #         t = t % q\n",
    "        # return -1\n",
    "        \n",
    "        # KMP\n",
    "        q = [-1] * m\n",
    "        i, j = 0, -1\n",
    "        while i < m - 1:\n",
    "            if needle[i + 1] == needle[j + 1]:\n",
    "                i, j = i + 1, j + 1\n",
    "                q[i] = j\n",
    "            elif j == -1:\n",
    "                i = i + 1\n",
    "                q[i] = -1\n",
    "            else:\n",
    "                j = q[j]\n",
    "        \n",
    "        i, j = -1, -1\n",
    "        while i < n - 1:\n",
    "            if haystack[i + 1] == needle[j + 1]:\n",
    "                i, j = i + 1, j + 1\n",
    "                if j == m - 1:\n",
    "                    return i - m + 1\n",
    "            elif j == -1:\n",
    "                i = i + 1\n",
    "            else:\n",
    "                j = q[j]\n",
    "        return -1\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack, needle):\n",
    "        \"\"\"\n",
    "        :type haystack: str\n",
    "        :type needle: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        if not needle: return 0\n",
    "        \n",
    "        if len(haystack) < len(needle):return -1\n",
    "        \n",
    "        res = -1\n",
    "        count = len(needle)\n",
    "        for i in range(len(haystack)):\n",
    "            \n",
    "            if haystack[i:i+count] == needle:\n",
    "                return i\n",
    "        return res\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#coding=gbk\n",
    "def kmp(s1,s2):\n",
    "\tn=len(s2)\n",
    "\tNextPair=[-1]\n",
    "\tt=-1\n",
    "\tfor q in range(1,n):\n",
    "\t\twhile t>-1 and s2[t+1]!=s2[q]:\n",
    "\t\t\tt=NextPair[t]\n",
    "\t\tif s2[t+1]==s2[q]:\n",
    "\t\t\tt+=1\n",
    "\t\tNextPair.append(t)\n",
    "\tfor i in range(len(NextPair)):\n",
    "\t\tNextPair[i]+=1\n",
    "\tm=len(s1)\n",
    "\ti=0\n",
    "\tif n==1:\n",
    "\t\tfor i,j in enumerate(s1):\n",
    "\t\t\tif j==s2:\n",
    "\t\t\t\treturn i\n",
    "\twhile i<=m-n:\n",
    "\t\tif s2[0] != s1[i]:\n",
    "\t\t\ti+=1\n",
    "\t\telse:\n",
    "\t\t\tfor j in range(1,n):\n",
    "\t\t\t\tif s2[j] != s1[i+j] :\n",
    "\t\t\t\t\tbreak\n",
    "\t\t\tif j==n-1 and s2[j]==s1[i+j]:\n",
    "\t\t\t\treturn i\n",
    "\t\t\telse:\n",
    "\t\t\t\ti+=j-NextPair[j-1]\n",
    "\treturn -1\n",
    "class Solution:\n",
    "\tdef strStr(self, haystack, needle):\n",
    "\t\tif needle==\"\":\n",
    "\t\t\treturn 0\n",
    "\t\telif haystack==\"\":\n",
    "\t\t\treturn -1\n",
    "\t\treturn kmp(haystack,needle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack, needle):\n",
    "        \"\"\"\n",
    "        :type haystack: str\n",
    "        :type needle: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if needle == \"\":\n",
    "            return 0\n",
    "        next = [0] * len(needle)\n",
    "        next[0] = -1\n",
    "        if len(needle) > 1:\n",
    "            next[1] = 0\n",
    "        i = 0\n",
    "        j = 1\n",
    "        while j < len(needle)-1:\n",
    "            if needle[j] == needle[i]:\n",
    "                next[j+1] = i + 1\n",
    "                j+=1\n",
    "                i += 1\n",
    "            else:\n",
    "                i = next[i]\n",
    "                if i == -1:\n",
    "                    i = 0\n",
    "                    next[j+1] = 0\n",
    "                    j += 1\n",
    "        i = 0\n",
    "        j = 0\n",
    "        print(next)\n",
    "        while i < len(haystack) and j < len(needle):\n",
    "            if haystack[i] == needle[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "                if j >= len(needle):\n",
    "                    return i - len(needle)\n",
    "            else:\n",
    "                j = next[j]\n",
    "                if j == -1:\n",
    "                    j = 0\n",
    "                    i += 1\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack, needle):\n",
    "        \"\"\"\n",
    "        :type haystack: str\n",
    "        :type needle: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if (len(needle)) == 0:\n",
    "            return 0       \n",
    "        # if haystack == needle:\n",
    "        #     return 0        \n",
    "        else:        \n",
    "            haystack_list  = [x for x in haystack]\n",
    "            idx = [i for i,x in enumerate(haystack_list) if x==needle[0]] \n",
    "            # 注意使用enumerate 取出多个值，list.index()只能取出第一个值\n",
    "            flag = 0\n",
    "            for id in idx:\n",
    "                if flag==0:\n",
    "                    loc_start = id\n",
    "                    loc_end = id + len(needle)\n",
    "                    # 这里注意loc_end不能超出haystack的长度范围\n",
    "                    if haystack[loc_start:loc_end] == needle:\n",
    "                        flag = 1\n",
    "                        id_res = id\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            return id_res if flag==1 else -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partial_table(self, p):\n",
    "        length = len(p)\n",
    "        res = [0 for i in range(length)]\n",
    "        j = 0\n",
    "        i = 1\n",
    "        while i < length:\n",
    "            if p[i] == p[j]:\n",
    "                res[i] = j + 1\n",
    "                i += 1\n",
    "\n",
    "                j += 1\n",
    "            else:\n",
    "                j = 0\n",
    "                i += max(res[i], 1)\n",
    "        return res\n",
    "\n",
    "    def strStr(self, s, p):\n",
    "        s_len = len(s)\n",
    "        p_len = len(p)\n",
    "        partial_table = self.partial_table(p)\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i + p_len <= s_len:\n",
    "            print(i, j)\n",
    "            if j >= p_len:\n",
    "                break\n",
    "            if s[i + j] == p[j]:\n",
    "                j += 1\n",
    "            else:\n",
    "                i += max(partial_table[j], 1)\n",
    "                j = 0\n",
    "\n",
    "        if j == p_len:\n",
    "            return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partial_table(self, p):\n",
    "        length = len(p)\n",
    "        res = [0 for i in range(length)]\n",
    "        j = 0\n",
    "        i = 1\n",
    "        while i < length:\n",
    "            if p[i] == p[j]:\n",
    "                res[i] = j + 1\n",
    "                i += 1\n",
    "\n",
    "                j += 1\n",
    "            else:\n",
    "                j = 0\n",
    "                i += max(res[i], 1)\n",
    "        return res\n",
    "\n",
    "    def strStr(self, s, p):\n",
    "        s_len = len(s)\n",
    "        p_len = len(p)\n",
    "        partial_table = self.partial_table(p)\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i + p_len <= s_len:\n",
    "            print(i, j)\n",
    "            if j >= p_len:\n",
    "                break\n",
    "            if s[i + j] == p[j]:\n",
    "                j += 1\n",
    "            else:\n",
    "                i += max(partial_table[j], 1)\n",
    "                j = 0\n",
    "\n",
    "        if j == p_len:\n",
    "            return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack, needle):\n",
    "        \"\"\"\n",
    "        :type haystack: str\n",
    "        :type needle: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if haystack==needle:return 0\n",
    "        if haystack and not (needle):return 0\n",
    "        next=self.get_next(needle)\n",
    "        print(next)\n",
    "        i=0\n",
    "        while(i<=len(haystack)-len(needle)):\n",
    "            if haystack[i]!=needle[0]:\n",
    "                i+=1\n",
    "            else:\n",
    "                j=0\n",
    "                while(j<len(needle) and haystack[i+j]==needle[j]):\n",
    "                    j+=1\n",
    "                if j==len(needle):\n",
    "                    return i\n",
    "                else:\n",
    "                    print(i,j,next[j-1])\n",
    "                    i+=(j-next[j-1])\n",
    "        return -1        \n",
    "        \n",
    "        \n",
    "    def get_next(self,needle):\n",
    "        next=[0]*len(needle)\n",
    "        k=0\n",
    "        for i in range(1,len(needle)):\n",
    "            while(k>0 and needle[i]!=needle[k]):\n",
    "                k=next[k-1]\n",
    "            if needle[i]==needle[k]:\n",
    "                k+=1\n",
    "            next[i]=k\n",
    "        return next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: 'str', needle: 'str') -> 'int':\n",
    "        import re\n",
    "        if re.search(needle, haystack):\n",
    "            return re.search(needle, haystack).span()[0]\n",
    "        else:\n",
    "            return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: 'str', needle: 'str') -> 'int':\n",
    "        if len(needle) == 0:\n",
    "            return 0\n",
    "        if haystack == needle:\n",
    "            return 0\n",
    "        if len(haystack) < len(needle):\n",
    "            return -1\n",
    "        for i in range(0, len(haystack) - len(needle)+1):\n",
    "            if needle == haystack[i:i+len(needle)]:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        if needle == '':\n",
    "            return 0\n",
    "        outcome = haystack.replace(needle, '*')\n",
    "        if len(outcome) <= len(haystack) and outcome != haystack:\n",
    "            i = 0\n",
    "            while outcome[i] != '*':\n",
    "                i = i + 1\n",
    "            return (i)\n",
    "        else:\n",
    "            return (-1)    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        if haystack==''and needle=='':\n",
    "            return 0\n",
    "        if haystack=='':\n",
    "            return -1\n",
    "        if needle=='':\n",
    "            return 0\n",
    "        for i in range(len(haystack)):\n",
    "            if haystack[i:i+len(needle)]==needle:\n",
    "                return i\n",
    "            elif i+len(needle)>=len(haystack):\n",
    "                return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        try:\n",
    "            return haystack.index(needle)\n",
    "        except :\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        if not needle:\n",
    "            return 0\n",
    "\n",
    "        h_length=len(haystack)\n",
    "        n_length=len(needle)\n",
    "\n",
    "        if n_length>h_length:\n",
    "            return -1\n",
    "\n",
    "        for i in range(h_length-n_length+1):            \n",
    "            for j in range(n_length):\n",
    "\n",
    "                if haystack[i+j]!=needle[j]:\n",
    "                    break\n",
    "                if j==n_length-1:\n",
    "                    return i\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        len_needle = len(needle)\n",
    "        len_hs = len(haystack)\n",
    "        if not needle :\n",
    "            return 0\n",
    "        if len_hs < len_needle:\n",
    "            return -1\n",
    "        for i in range(len_hs - len_needle +1):\n",
    "            if haystack[i] == needle[0]:\n",
    "                if haystack[i:i+len_needle] == needle:\n",
    "                    return i\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        L, n = len(needle), len(haystack)\n",
    "        if L == 0:\n",
    "            return 0\n",
    "        pn = 0\n",
    "        while pn < n - L + 1:\n",
    "\n",
    "            while pn < n - L + 1 and haystack[pn] != needle[0]:\n",
    "                pn += 1\n",
    "\n",
    "            curr_len = pL = 0\n",
    "            while pL < L and pn < n and haystack[pn] == needle[pL]:\n",
    "                pn += 1\n",
    "                pL += 1\n",
    "                curr_len += 1\n",
    "\n",
    "            if curr_len == L:\n",
    "                return pn - L\n",
    "            \n",
    "            pn = pn - curr_len + 1\n",
    "            \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        if len(needle) == 0:\n",
    "            return 0\n",
    "        if len(haystack) == 0 or len(haystack) < len(needle):\n",
    "            return -1\n",
    "\n",
    "        length = len(needle)\n",
    "        for i in range(0, len(haystack) - length+1):\n",
    "            if haystack[i:i + length] == needle:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        return haystack.find(needle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "            '''\n",
    "            return haystack.find(needle)\n",
    "            \n",
    "            for i in range(len(haystack)-len(needle)+1):\n",
    "                for j in range(len(needle)):\n",
    "                    if haystack[i+j]!=needle[j]:\n",
    "                        break\n",
    "                else:\n",
    "                    return i\n",
    "            return -1\n",
    "            '''\n",
    "            for i in range(len(haystack)-len(needle)+1):\n",
    "                if haystack[i:i+len(needle)]==needle:\n",
    "                    return i\n",
    "            else:\n",
    "                return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        if len(needle) == 0:\n",
    "            return 0\n",
    "        if len(haystack) == 0:\n",
    "            return -1\n",
    "        def RK(s, p):\n",
    "            from functools import reduce\n",
    "            c = int(128)\n",
    "            mod = int(1e9 + 7)\n",
    "            n, m = len(s), len(p)\n",
    "            w = pow(c, m - 1, mod)\n",
    "            hashp = reduce(lambda x, y: (x * c + y) % mod, [ord(i) for i in p])\n",
    "            hashs = 0\n",
    "            for i in range(n):\n",
    "                if i < m:\n",
    "                    hashs = (hashs * c + ord(s[i])) % mod\n",
    "                else:\n",
    "                    hashs = ((hashs - w * ord(s[i - m])) % mod * c + ord(s[i]) ) % mod\n",
    "                if i >= m - 1 and hashs == hashp:\n",
    "                    return i - m + 1\n",
    "            return -1\n",
    "        return RK(haystack, needle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        if not needle: return 0\n",
    "        haystack=list(haystack)\n",
    "        needle=list(needle)\n",
    "        n=len(needle)\n",
    "\n",
    "       \n",
    "  \n",
    "        for index,item in enumerate(haystack):\n",
    "            if item==needle[0]:\n",
    "                cut=haystack[index:index+n]\n",
    "                if cut==needle:return index\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def strStr(self, haystack: str, needle: str) -> int:\n",
    "        # 解法1：遍历字符串，当两个子串的第一个字符相等的时候，再进行字符串的匹配，在匹配的过程中，一旦发现两个字符不相等，停止匹配之后的字符，继续遍历字符串，寻找满足题意的子串。\n",
    "        # 1.1 循环遍历\n",
    "        # if(not haystack and needle): return -1 \n",
    "        # if(not needle or not haystack): return 0 \n",
    "        # length = len(needle)\n",
    "        # if(length > len(haystack)): return -1 \n",
    "        # for i in range(len(haystack)):\n",
    "        #     if(haystack[i]!=needle[0]):\n",
    "        #         continue \n",
    "        #     else:\n",
    "        #         for j in range(length):\n",
    "        #             if(i+j>=len(haystack) or haystack[i+j]!=needle[j]):\n",
    "        #                 break \n",
    "        #             if(j==length-1): return i \n",
    "        # return -1 \n",
    "\n",
    "        # 1.2 双指针法\n",
    "        # L, l = len(haystack), len(needle)\n",
    "        # if(l==0): return 0 \n",
    "        # p1, p2 = 0, 0\n",
    "        # while(p1<L-l+1):\n",
    "        #     if(haystack[p1]!=needle[p2]):\n",
    "        #         p1 += 1\n",
    "        #     else:\n",
    "        #         while(p2<l):\n",
    "        #             if(haystack[p1]==needle[p2]):\n",
    "        #                 if(p2==l-1): return p1-l+1\n",
    "        #                 p1 += 1\n",
    "        #                 p2 += 1\n",
    "        #             else:\n",
    "        #                 break\n",
    "        #         p1, p2 = p1-p2+1, 0\n",
    "        # return -1\n",
    "\n",
    "        # 解法2：滑窗比较，每次直接比较两个子串是否相等。\n",
    "        # L,l = len(haystack), len(needle)\n",
    "        # for i in range(L-l+1):\n",
    "        #     if(haystack[i:i+l]==needle): return i \n",
    "        # return -1 \n",
    "\n",
    "    # 解法3：KMP算法。思想：根据模式串构建next数组，之后根据next数组进行模式匹配。\n",
    "    # 如何构建next数组？从左到右遍历，当前遍历位置的值由已经遍历到的字符组成的字符串决定，确定的规则是找到其前缀串和后缀串匹配长度的最大值。\n",
    "    # 如何利用next数组进行匹配？在匹配字符串的时候，如果某个位置出现了字符不匹配的情况，先查询当前模式串当前字符对应位置的next数组中的值，根据该值向后移动模式串，而不是每一次都向后移动一个字符。\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        if(not needle): return 0 \n",
    "        next = self.gen_next_arr(needle)\n",
    "        L, l = len(haystack), len(needle)\n",
    "        p1, p2 = 0, 0\n",
    "        # 最后一个用例超时了\n",
    "        # next = self.gen_next_arr(needle)\n",
    "        # print(L-l+1)\n",
    "        # move_value = 0\n",
    "        # while(p1-move_value<L-l+1):\n",
    "        #     while(p2<l):\n",
    "        #         if(haystack[p1]!=needle[p2]):\n",
    "        #             if(p2==0):\n",
    "        #                 move_value = next[1]\n",
    "        #                 p1 += 1 \n",
    "        #             else:\n",
    "        #                 move_value = next[p2]\n",
    "        #             p2 = move_value\n",
    "        #             break \n",
    "        #         else:\n",
    "        #             if(p2==l-1): return p1-p2\n",
    "        #             p1 += 1\n",
    "        #             p2 += 1  \n",
    "        # return -1\n",
    "        # 参考题解的解法\n",
    "        while(p1<L and p2<l):\n",
    "            if(p2==-1 or haystack[p1]==needle[p2]):\n",
    "                p1 += 1\n",
    "                p2 += 1\n",
    "            else:\n",
    "                p2 = next[p2]\n",
    "        if(p2==l): return p1-p2\n",
    "        return -1        \n",
    "\n",
    "    # def gen_next_arr(self, s): # aabaaf\n",
    "    #     next = [] # 长度为len(s)\n",
    "    #     next.append(-1)\n",
    "    #     next.append(0)\n",
    "    #     for i in range(1, len(s)):\n",
    "    #         sub_s = s[0:i+1]\n",
    "    #         max_length = 0\n",
    "    #         # 依次判断长度为1到n-1的n-1对前缀串和后缀串是否相等\n",
    "    #         for j in range(1, len(sub_s)):\n",
    "    #             if(sub_s[0:j]==sub_s[-j:]):\n",
    "    #                 max_length = j\n",
    "    #         next.append(max_length)\n",
    "    #     return next\n",
    "    def gen_next_arr(self, p): \n",
    "        \"\"\" 构造子串needle的匹配表, 以 \"ABCDABD\" 为例\n",
    "        i         i          i           i            i             i             i\n",
    "        ABCDABD  ABCDABD   ABCDABD    ABCDABD     ABCDABD      ABCDABD      ABCDABD\n",
    "        ABCDABD   ABCDABD    ABCDABD     ABCDABD      ABCDABD      ABCDABD        ABCDABD\n",
    "        j         j          j           j            j             j             j\n",
    "        \"\"\"\n",
    "        _next = [0] * (len(p)+1) #      A  B  C  D  A  B  D\n",
    "        _next[0] = -1            # [-1, 0, 0, 0, 0, 1, 2, 0]\n",
    "        i, j = 0, -1\n",
    "        while (i < len(p)):\n",
    "            if (j == -1 or p[i] == p[j]):\n",
    "                i += 1\n",
    "                j += 1 \n",
    "                _next[i] = j\n",
    "            else:\n",
    "                j = _next[j]\n",
    "        return _next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        l1=len(haystack)\n",
    "        l2=len(needle)\n",
    "        if l1<l2:\n",
    "            return -1\n",
    "        if l1==l2 and haystack==needle:\n",
    "            return 0\n",
    "        for i in range(l1-l2+1):\n",
    "            if haystack[i:i+l2]==needle:\n",
    "                return i \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        # =========================暴力====================\n",
    "        # if needle in haystack:\n",
    "        #     return haystack.index(needle)\n",
    "        # else:\n",
    "        #     return -1\n",
    "\n",
    "        # =========================遍历=====================\n",
    "        for i in range(len(haystack)):\n",
    "\n",
    "            if haystack[i] == needle[0]:\n",
    "                for j in range(len(needle)):                    \n",
    "                    if i+j >= len(haystack) or haystack[i+j] != needle[j]:\n",
    "                        break\n",
    "                    if j == len(needle)-1:\n",
    "                        return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        # =========================暴力====================\n",
    "        # if needle in haystack:\n",
    "        #     return haystack.index(needle)\n",
    "        # else:\n",
    "        #     return -1\n",
    "\n",
    "        # =========================遍历=====================\n",
    "        # for i in range(len(haystack)):\n",
    "        #     if haystack[i] == needle[0]:\n",
    "        #         for j in range(len(needle)):   # ==============从0开始，避免只有一个字符\n",
    "        #             if i+j >= len(haystack) or haystack[i+j] != needle[j]:\n",
    "        #                 break  # ============================h的下标大于长度时，或者不相等，不符合\n",
    "        #             if j == len(needle)-1:\n",
    "        #                 return i\n",
    "        # return -1\n",
    "\n",
    "        # =========================KMP======================\n",
    "        def getnext(s):\n",
    "            # 初始化，i在循环中初始化\n",
    "            Next = [0]*len(s)\n",
    "            j = 0\n",
    "            Next[0] = 0\n",
    "            for i in range(1, len(s)):\n",
    "\n",
    "                # 处理前后缀不同的情况\n",
    "                while (j > 0 and s[j] != s[i]):\n",
    "                    j = Next[j-1]\n",
    "\n",
    "                # 处理前后缀相同的情况\n",
    "                if s[j] == s[i]:\n",
    "                    j += 1\n",
    "\n",
    "                # 更新Next数组\n",
    "                Next[i] = j\n",
    "\n",
    "            return Next\n",
    "\n",
    "        Next = getnext(needle)\n",
    "        j = 0\n",
    "\n",
    "        for i in range(len(haystack)):\n",
    "            # 如果不同，j回退\n",
    "            while j>0 and haystack[i] != needle[j]:\n",
    "                j = Next[j-1]\n",
    "            \n",
    "            # 如果相同，j自增\n",
    "            if haystack[i] == needle[j]:\n",
    "                j += 1\n",
    "\n",
    "            # 如果j到最后，说明完全匹配上了\n",
    "            if j == len(needle):\n",
    "                return i - len(needle) + 1\n",
    "\n",
    "        return -1\n",
    "               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        next = [-1] * len(needle)\n",
    "        j = 0\n",
    "        i = 1\n",
    "        while i < len(needle):\n",
    "            # print(i, j, needle[i])\n",
    "            if next[i] == -1:\n",
    "                next[i] = j\n",
    "\n",
    "            if needle[i] == needle[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                j = next[j]\n",
    "                if j == -1:\n",
    "                    i += 1\n",
    "                    j = 0\n",
    "        \n",
    "        print(needle, next)\n",
    "        i = 0\n",
    "        pos = 0\n",
    "        # for pos, h in enumerate(haystack):\n",
    "        while pos < len(haystack):\n",
    "            h = haystack[pos]\n",
    "            print(pos, h, needle[i], i)\n",
    "            if h == needle[i]:\n",
    "                i += 1\n",
    "                if i == len(needle):\n",
    "                    return pos - len(needle) + 1\n",
    "                pos += 1\n",
    "            else:\n",
    "                i = next[i]\n",
    "            if i == -1:\n",
    "                i = 0\n",
    "                pos += 1\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        i = 0\n",
    "        while i < len(haystack):\n",
    "            j = 0\n",
    "            while j < len(needle) and i+j < len(haystack) and haystack[i+j] == needle[j]:\n",
    "                j += 1\n",
    "            if j==len(needle):\n",
    "                return i\n",
    "            i += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        n = len(needle)\n",
    "        for i in range(len(haystack) - n + 1):\n",
    "            if haystack[i: i + n] == needle:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        if len(needle) > len(haystack):\n",
    "            return -1\n",
    "        return haystack.find(needle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        lenHay = len(haystack)\n",
    "        lenNeedle = len(needle)\n",
    "        if lenNeedle > lenHay:\n",
    "            return -1 \n",
    "\n",
    "        prefixtable = self.getTable(needle, lenNeedle)\n",
    "        \n",
    "        j = -1\n",
    "        for i in range(lenHay):\n",
    "            while j > -1 and haystack[i] != needle[j + 1]:\n",
    "                j = prefixtable[j]\n",
    "            if haystack[i] == needle[j + 1]:\n",
    "                j += 1\n",
    "            if j == lenNeedle - 1:\n",
    "                return i - lenNeedle + 1\n",
    "        return -1\n",
    "\n",
    "    def getTable(self, needle, lenNeedle):\n",
    "        table = [\"\" for _ in range(lenNeedle)]\n",
    "        j = -1\n",
    "        table[0] = j\n",
    "        for i in range(1, lenNeedle):\n",
    "            while j > -1 and needle[i] != needle[j + 1]:\n",
    "                j = table[j]\n",
    "            if needle[i] == needle[j + 1]:\n",
    "                j += 1\n",
    "            table[i] = j\n",
    "        return table"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
